Metode numerice - Aplicatii

Lucrarea 8.   Ecuatii neliniare: metode de partitionare si metode de aproximatii succesive

Index:     Tema A - Metode de partitionare
                    A.1. Metoda bisectiei          <----------- algoritm
                    A.2. Metoda secantei         <----------- algoritm
              Tema B - Metode de aproximatii succesive
                    B.1. Metoda contractiei      <----------- algoritm
                    B.2. Metoda Newton          <----------- algoritm

        Orice ecuatie care nu are forma a * x+b=0 se numeste neliniara si se exprima sintetic:

f(x) = 0
Daca functia f(x) are forma unui polinom sau poate fi adusa la aceasta forma, ecuatia se numeste algebrica. In  caz contrar - cand f(x) are o forma oarecare - ecuatia se numeste transcendenta. De exemplu functiile:
genereaza ecuatii algebrice, in timp ce functiile:
genereaza ecuatii transcendente.
        Un punct  din intervalul de definitie al lui f(x) cu proprietatea f(  )=0 se numeste zerou al functiei f(x) sau radacina a ecuatiei f(x)=0.
        Metodele de rezolvare a ecuatiilor neliniare au toate caracter iterativ si se impart in doua mari categorii: metode de partitionare si metode de aproximatii succesive.
        Pentru metodele de partitionare, folosind principiul partitionarii, intervalul de lucru este micsorat progresiv, pana la o deschidere suficient de mica pentru a satisface precizia impusa. Metodele din aceasta categorie (metoda bisectiei sau metoda secantei) sunt metode sigure - in sensul in care radacina este intotdeauna izolata intr-un interval suficient de ingust - dar se caracterizeaza printr-o convergenta lenta.
       Metodele de aproximatii succesive pornesc de la o aproximatie initiala, pe care o imbunatatesc in pasi succesivi si, in anumite conditii, converg catre solutia exacta. Metoda contractiei si metoda Newton sunt principalele metode de acest tip, dar exista o gama larga de variante ale lor, concepute in scopul imbunatatirii performantelor. Metodele de aproximatii succesive sunt, de regula, mai rapide decat metodele de partitionare, dar prezinta riscul divergentei atunci cand in vecinatatea zeroului cautat, functia f(x) are o comportate specifica.

Tema A - Metode de partitionare

        Dupa incadrarea unei solutii exacte, se pot aplica o serie de metode iterative care permit determinarea unei solutii aproximative in limita preciziei impuse. Dintre acestea, metodele de partitionare actioneaza direct asupra intervalului in care a fost incadrata solutia, urmarind "comprimarea" acestuia pana la limita impusa de criteriul de oprire. Din aceasta categorie fac parte metoda bisectiei, metoda secantei si metoda cautarii cu pas variabil. Deoarece la fiecare iteratie, intervalul de lucru incadreaza permanent solutia exacta, convergenta acestor metode este garantata. Din pacate, ele se caracterizeaza printr-un numar mare de iteratii necesare atingerii preciziei impuse, deci prin timpi de calcul mari.

  Inapoi la index

        Metoda bisectiei

        Metoda bisectiei, numita uneori si metoda dihotomiei sau a injumatatirii intervalelor, este cea mai simpla dintre metodele de rezolvare a ecuatiilor algebrice si transcendente. Se considera ca, printr-un procedeu oarecare, s-a reusit localizarea radacinii exacte  a ecuatiei f(x)=0 in intervalul [,]. In ipoteza in care functia f(x) este continua, iar radacina  este singurul zerou al lui f(x) in [,], la extremitatile intervalului functia ia valori de semne contrare: f() * f()<0.

        Determinarea aproximatiei ' a radacinii exacte  cu o precizie  folosind metoda bisectiei foloseste urmatoarea schema (vezi si figura de mai sus): intervalul [,] se injumatateste prin punctul m=(+)/2 si se calculeaza produsul f(m) * f(). Daca f(m) * f() este pozitiv, radacina  se gaseste intre si m.In acest caz, se retine valoarea lui m ca extremitatea dreapta a intervalului (<-- m) si se reia procedeul. Daca f(m) * f() este negativ, radacina  se gaseste intre m si . De aceasta data, se modifica extremitatea stanga a intervalului (<-- m) si se reia procedeul. Aceasta schema se aplica in mod repetat pana cand lungimea intervalului [,] - modificat de la o iteratie la alta - scade sub valoarea limita 2*, adica - < 2*. Daca, in acest moment, se considera ca radacina aproximativa '=(+)/2, acesta nu se indeparteaza de solutia exacta  cu mai mult de . Desigur, intr-un caz banal, este  posibil ca, in cursul injumatatirii intervalelor succesive [,], punctul m sa coincida cu radacina exacta . Aceasta situatie se recunoaste prin anularea produsului f(m) * f(), caz in care schema de calcul se intrerupe, dispunand in acest caz chiar de radacina exacta '=m=.


Algoritmul 1 - Ecuatii neliniare - Metoda bisectiei
  1. Definirea functiei f(x), a intervalului de lucru [,], a preciziei si a numarului maxim de iteratii Nmax.
  2. Procesul iterativ:
    1. Initializarea procesului iterativ: It <-- 0;
    2. Daca s-a atins precizia doritta (- < 2*) sau numarul maxim de iteratii Nmax se incheie bucla iterativa si se trece la pasul 3.
    3. Se trece la o noua iteratie: It <-- It+1;
    4. Injumatatirea intervalului curent: m <-- (+)/2 ;
    5. Stabilirea noului interval de lucru:
      1. Daca f(m) * f()<0, radacina se gaseste in [m , ]; se actualizeaza limita stanga: <-- m si se trece la pasul 2.vi;
      2. Daca f(m) * f()>0, radacina se gaseste in [ , m]; se actualizeaza limita dreapta: <-- m si se trece la pasul 2.vi;
      3. Daca f(m) * f()=0, radacina este m; se actualizeaza ambele limite: <-- m,<-- m si se trece la pasul 2.vi;
    6. Se revine la pasul 2.ii;
  3. Calculul radacinii aproximative: x <-- (+)/2.

  Inapoi la index

        Metoda secantei

        Metoda secantei, numita si metoda partilor proportionale, restrange intervalul [,] ce incadreaza solutia exacta in iteratia curenta prin raportarea la valorile functiei la extremitatile intervalului. Astfel, daca noua aproximatie x se alege astfel incat solutia exacta sa se gaseasca in intervalul [, x], valoarea lui x rezulta din egalitatea proportiilor:

Interpretarea geometrica a acestei relatii corespunde constructiei din figura. Astfel, pe intervalul [,] curba y=f(x) este aproximata prin dreapta ce trece prin cele doua puncte A si B de la extremitatile intervalului. In aceste conditii, solutia exacta () urmeaza a fi aproximata prin abscisa punctului de intersectie a dreptei AB  cu axa OX, notata cu x. Noua aproximatie x se determina impunand conditia ca in ecuatia dreptei  AB :

punctul (x,y) sa se gaseasca pe axa OX, adica y=0:
In continuare, dintre intervalele [, x ] si [ x ,] se retine acela ce incadreaza solutia  - acel interval la extremitatile caruia functia f(x) ia valori de semne contrare. Aplicand o relatie asemenatoare noului interval se obtine o noua aproximatie a solutiei exacte si procesul continua pana la satisfacerea unui criteriu de oprire.


Algoritmul 2 - Ecuatii neliniare - Metoda secantei
  1. Definirea functiei f(x), a intervalului de lucru [, ], a preciziei si a numarului maxim de iteratii Nmax.
  2. Procesul iterativ:
    1. Initializarea procesului iterativ: It <-- 0;
    2. Daca s-a atins precizia dorita (- < 2*) sau numarul maxim de iteratii Nmax se incheie bucla iterativa si se trece la pasul 3.
    3. Se trece la o noua iteratie: It <-- It+1;
    4. Calculul noii aproximatii:
    5. Stabilirea noului interval de lucru:
      1. Daca f(m) * f()<0, radacina se gaseste in [ x,]; se actualizeaza limita stanga:<-- x si se revine la pasul 2.ii.
      2. Daca f(m) * f()>0, radacina se gaseste in [,x]; se actualizeaza limita dreapta:<-- x si se revine la pasul 2.ii.
      3. Daca f(m) * f()=0, radacina este x; se actualizeaza ambele limite: <-- x, <-- x si se revine la pasul 2.ii.
  3. Calculul radacinii aproximative: x <-- (+ )/2.

  Inapoi la index

Tema B - Metode de aproximatii succesive

        Dupa cum reiese si din numele lor, metodele de aproximatii succesive determina o solutie aproximativa a unei ecuatii neliniare prin construirea unui sir de aproximatii succesive care, in anumite conditii, converge catre solutia exacta. De aceasta data nu se mai actioneaza asupra intervalului in care a fost izolata solutia exacta. Acest interval este folosit numai pentru stabilirea aproximatiei initiale, care poate fi aleasa, in principiu, oriunde in interiorul acestuia. Din categoria metodelor de aproximatii succesive fac parte metoda contractiei si metoda Newton.
O caracteristica a metodelor de aproximatii succesive se refera la interpretarea geo- metrica ce se asociaza procesului iterativ. Pentru metodele de partitionare, rezolvarea ecuatiei f(x)=0 se face prin determinarea din aproape in aproape, pana la o precizie impusa, a punc- tului de intersectie a curbei y=f(x) cu axa absciselor. Metodele de aproximatii succesive inlocuiesc ecuatia sub forma implicita f(x)=0 cu o ecuatie echivalenta exprimata insa explicit:

a carei rezolvare presupune determinarea punctului de intersectie a curbelor; y=(x) si y=g(x). Din considerente de simplificare a calculelor, se cauta ca expresiile functiilor (x) si g(x) sa aiba o complexitate cat mai redusa posibil. In acest sens, cele mai raspandite metode utilizeaza un caz particular al ecuatiei explicite, si anume, acela pentru care curba y = (x) se reduce la o dreapta, iar ecuatia explicita capata forma:
        Determinarea radacinii  aproximative se face pornind de la o aproximatie initiala x_0, corectata apoi succesiv folosind o formula de recurenta de forma:
        Daca sirul aproximatiilor succesive este convergent, el tinde catre solutia exacta a ecuatiilor echivalente f(x)=0, respectiv x=g(x). Diferitele metode de aproximatii succesive folosite in practica se deosebesc prin modul de construire a ecuatiei explicite, in particular, prin alegerea functiei g(x), alegere care determina si conditiile  specifice de convergenta. In comparatie cu metodele de partitionare, convergenta metodelor de aproximatii succesive este, de regula, mai rapida, dar din pacate nu intotdeauna asigurata.

  Inapoi la index

       Metoda contractiei

        Inlocuirea ecuatiei  f(x)=0 printr-o ecuatie explicita x=g(x) se poate realiza, de regula, pe mai multe cai. Cea mai simpla dintre acestea determina functia g(x) sub forma:

g(x) = x + f(x)
In continuare, vom considera ca metoda contractiei, numita uneori impropriu si metoda  aproximatiilor succesive, este generata de functia g(x) de aceasta forma. Sirul aproximatiilor succesive este generat pornind de la aproximatia initiala x_0 , cu relatia de recurenta:
        Se poate arata ca intre erorile de aproximare in doua iteratii succesive e_n si e_(n+1) exista relatia :
care permite stabilirea unei forme primare a conditiei de convergenta. Astfel, pentru ca sirul aproximatiilor succesive sa fie convergent, eroarea de  aproximare trebuie sa scada  intre doua iteratii consecutive, adica  |e_(n+1)|  < |e_n|, ceea ce conduce la |g'()| < 1. Aceasta reprezinta o conditie necesara, dar nu si suficienta pentru asigurarea convergentei. O valoare subunitara in modul a derivatei g'() garanteaza existenta unui interval [,], in jurul solutiei exacte , in care poate fi aleasa aproximatia initiala x_0, astfel incat procesul iterativ sa fie convergent. De fapt, o conditie de forma |g'(x)| < 1 trebuie satisfacuta in intregul interval [,]. Chiar daca conditia |g'()| < 1 este satisfacuta, dar aproximatia initiala este aleasa departe de solutia exacta , structura functiei  g(x) poate conduce la un proces divergent.
        Convergenta procesului iterativ este guvernata de o teorema de punct fix care, in principiu, impune urmatoarele conditii:  pentru un interval  [,], oricat de larg, alegerea unei aproximatii initiale x_0  in interiorul acestuia,  care sa  asigure convergenta, este arbitrara daca si numai daca functia  g(x) este o aplicatie strict contractanta pe acel interval (vezi figura de mai jos).
Interpretarea geometrica a notiunii de "aplicatie strict contractanta". (a) Functia g(x) este o aplicatie strict contractanta pe un anumit interval daca proiectia acestui interval pe axa Oy, prin curba y = g(x) se contracta. (b) In caz contrar, cand proiectia intervalului respectiv pe axa Oy, prin curba y = g(x) se dilata, g(x) nu mai este o aplicatie strict contractanta.
        Evolutia unor procese iterative convergente sau divergente este ilustrata in figura de mai jos. In functie de semnul derivatei g' in vecinatatea solutiei , convergenta poate fi monotona (cazurile a si b), pentru g'()>0, sau oscilanta (cazurile c si d), pentru g'()<0. De asemenea, in cazurile e si f sunt prezentate doua procese divergente, unul monoton si celalalt oscilant. Cazul |g'()|=1 este deosebit de sensibil deoarece, in functie de forma curbei y=g(x), se poate obtine atat convergenta (cazul g), cat si divergenta (cazul h) sirului aproximatiilor succesive.

Convergenta monotona












  Inapoi

Convergenta oscilanta












  Inapoi

Divergenta












  Inapoi

Cazul |g'()|=1












  Inapoi

        Verificarea conditiilor teoremei de punct fix este insa o sarcina mult prea neproductiva din punctul de vedere al timpului de calcul si al complexitatii calculelor pentru a fi si practica. Se prefera verificarea, cel mult, a unei conditii de forma |g'()| < 1 si localizarea stricta a solutiei , iar cel mai frecvent se impune un numar maxim de iteratii la epuizarea carora procesul iterativ este intrerupt fortat.


Algoritmul 3 - Ecuatii neliniare - Metoda contractiei
  1. Definirea functiei f(x), a aproximatiei initiale x, a preciziei Eps si a numarului maxim de iteratii Nmax.
  2. Construirea functiei g(x) = x + f(x).
  3. Procesul iterativ:
    1. Initializarea procesului iterativ: It <-- 0;
    2. Daca s-a atins precizia dorita (|f(x)|<Eps) sau numarul maxim de iteratii (It=Nmax) se intrerupe bucla iterativa si se trece la pasul 4.
    3. Se trece la o noua iteratie: It <-- It+1;
    4. Calculul noii aproximatii: x <-- g(x)
    5. Se revine la pasul 3.2.
  4. Stabilirea conditiilor de iesire din bucla iterativa:
    • Daca |f(x)|<Eps - proces convergent - solutia aproximativa este x.
    • Daca |f(x)|>=Eps si It=Nmax, se afiseaza mesajul "Depasire numar maxim iteratii".

  Inapoi la index

        Metoda Newton

        Una dintre cele mai cunoscute si mai folosite tehnici de rezolvare a ecuatiilor neliniare este metoda Newton, denumita uneori si metoda Newton-Raphson sau metoda tangentelor. Ea se deosebeste de alte metode de aproximatii succesive prin faptul ca pentru fiecare punct din sirul aproximatiilor este necesara atat evaluarea functiei f(x) ce defineste ecuatia, cat si a derivatei acesteia f '(x).

        Valoarea aproximativa a radacinii exacte  se calculeaza folosind un sir de aproximatii succesive {x_0, x_1, x_2, ... } construit dupa urmatorul model. Pornind de la aproximatia x_0, curba y=f(x) este aproximata in punctul de coordonate (x_0, f(x_0)) prin tangenta la ea. Noua aproximatie x_1 se obtine la intersectia acestei tangente cu axa absciselor. Folosind pe x_1 ca aproximatie initiala, se reia procedeul, determinandu-se o noua aproximatie x_2 s.a.m.d. pana cand abaterea intre doua iteratii succesive scade sub o valoare prag impusa: |x_(n+1) - x_n| <.
Alegerea aproximatiei initiale influenteaza in buna masura procesul iterativ. (a) Daca aproximatia initiala este prea departe de solutia exacta, este posibil ca, datorita unei forme aparte a curbei y = f(x), noile aproximatii sa fie aruncate spre infinit. (b) Intr-o situatie mai fericita, procesul ramane convergent, dar sirul aproximatiilor succesive se indreapta catre o alta radacina decat cea cautata.
        Din punct de vedere formal, metoda Newton foloseste formula de recurenta (iterare):
        Conditiile de convergenta ale metodei Newton sunt relativ complexe ca forma si se refera nu numai la functia f(x), ci si la primele sale doua derivate, f '(x) si f ''(x).
        Marele avantaj al metodei Newton este rata mare de convergenta. In apropierea solutiei exacte, se asigura practic dublarea numarului de cifre exacte ale solutiei calculate la fiecare iteratie. Aceasta proprietate remarcabila este "cartea de vizita" ce recomanda metoda Newton ca fiind cea mai eficienta cale de rezolvare a unei ecuatii neliniare pentru care este posibila evaluarea derivatei f '(x). Remarcati totusi precizarea din fraza anterioara ("In apropierea solutiei exacte...") si nu uitati conditiile de convergenta atat de alambicate, care se refera atat la functia f(x), cat si la primele sale doua derivate. Din aceste cauze, despre metoda Newton se spune ca are proprietati locale de convergenta foarte bune, dar se poate comporta lamentabil la nivel global. In situatiile din urma metoda Newton poate fi aplicata ca o procedura terminala, pentru  rafinarea eficienta si foarte rapida a unei aproximatii obtinute prin aplicarea, in prima faza, a unei alte metode, mai putin sensibile din punctul de vedere al convergentei dar, in principiu, mai lenta.


Algoritmul 4 - Ecuatii neliniare - Metoda Newton
  1. Definirea functiei f(x), a derivatei f '(x), a aproximatiei initiale x, a preciziei Eps si a numarului maxim de iteratii Nmax.
  2. Initializarea procesului iterativ: It <-- 0;
  3. Procesul iterativ:
    1. Se trece la o noua iteratie: It <-- It+1;
    2. Calculul corectiei: dx <--  - f(x) / f '(x)
    3. Calculul noii aproximatii: x <-- x + dx
    4. Daca s-a atins precizia dorita (|dx| <= Eps) sau numarul maxim de iteratii (It=Nmax) se intrerupe bucla iterativa si se trece la pasul 4.
    5. Se revine la pasul 3.1.
  4. Stabilirea conditiilor de iesire din bucla iterativa:
    • Daca |dx|<Eps - proces convergent - solutia aproximativa este x.
    • Daca |dx|>=Eps si It=Nmax, se afiseaza mesajul "Depasire numar maxim iteratii".

  Inapoi la index

Pentru detalii suplimenatare privind metodele de rezolvare a ecuatiilor neliniare, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".
 

   Aplicatii - Lista lucrarilor de laborator